|
The algebraic connectivity of a graph ''G'' is the second-smallest eigenvalue of the Laplacian matrix of ''G''.〔Weisstein, Eric W. "(Algebraic Connectivity )." From MathWorld--A Wolfram Web Resource.〕 This eigenvalue is greater than 0 if and only if ''G'' is a connected graph. This is a corollary to the fact that the number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph. The magnitude of this value reflects how well connected the overall graph is, and has been used in analysing the robustness and synchronizability of networks. == Properties == The algebraic connectivity of a graph ''G'' is greater than 0 if and only if ''G'' is a connected graph. Furthermore, the value of the algebraic connectivity is bounded above by the traditional (vertex) connectivity of the graph.〔J.L. Gross and J. Yellen. ''Handbook of Graph Theory'', CRC Press, 2004, page 314.〕 If the number of vertices of a connected graph is ''n'' and the diameter is ''D'', the algebraic connectivity is known to be bounded below by ,〔J.L. Gross and J. Yellen. ''Handbook of Graph Theory'', CRC Press, 2004, page 571.〕 and in fact (in a result due to Brendan McKay) by .〔Bojan Mohar, (The Laplacian Spectrum of Graphs ), in ''Graph Theory, Combinatorics, and Applications'', Vol. 2, Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk, Wiley, 1991, pp. 871–898.〕 For the example shown above, 4/18 = 0.222 ≤ 0.722 ≤ 1. Unlike the traditional connectivity, the algebraic connectivity is dependent on the number of vertices, as well as the way in which vertices are connected. In random graphs, the algebraic connectivity decreases with the number of vertices, and increases with the average degree.〔(Synchronization and Connectivity of Discrete Complex Systems ), Michael Holroyd, International Conference on Complex Systems, 2006.〕 The exact definition of the algebraic connectivity depends on the type of Laplacian used. Fan Chung has developed an extensive theory using a rescaled version of the Laplacian, eliminating the dependence on the number of vertices, so that the bounds are somewhat different.〔F. Chung. ''Spectral Graph Theory'', Providence, RI: Amer. Math. Soc., 1997.()〕 In models of synchronization on networks, such as the Kuramoto model, the Laplacian matrix arises naturally, and so the algebraic connectivity gives an indication of how easily the network will synchronize.〔Tiago Pereira, ''(Stability of Synchronized Motion in Complex Networks )'', arXiv:1112.2297v1, 2011.〕 However, other measures, such as the average distance (characteristic path length) can also be used,〔D. Watts, ''Six Degrees: The Science of a Connected Age'', Vintage, 2003.〕 and in fact the algebraic connectivity is closely related to the (reciprocal of the) average distance.〔 The algebraic connectivity also relates to other connectivity attributes, such as the isoperimetric number, which is bounded below by half the algebraic connectivity.〔Norman Biggs. ''Algebraic Graph Theory'', 2nd ed, Cambridge University Press, 1993, pp. 28 & 58.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Algebraic connectivity」の詳細全文を読む スポンサード リンク
|